package bin_tree.searchtree;

import java.util.NoSuchElementException;

/**
 * @author zerorain
 * @date 2022/03/18 13:41
 * 基于整型的二叉搜索树
 **/
public class BST {
        private class TreeNode {
            private int val;
            private TreeNode left;
            private TreeNode right;
            public TreeNode(int val) {
                this.val = val;
            }
        }
        private int size;
        private TreeNode root;

        public void add(int val) {
            root = add(root,val);
        }

        /**
         * 判断当前树中是否存在val
         * @param val
         * @return
         */
        public boolean contains(int val) {
            return contains(root,val);
        }

        /**
         * 判断当前以root为根的BST中是否包含了val
         * @param root
         * @param val
         * @return
         */
        private boolean contains(TreeNode root, int val) {
            // 边界
            if (root == null) {
                return false;
            }
            if (root.val == val) {
                // 找到了
                return true;
            }else if (val < root.val) {
                // 递归去左树中查找
                return contains(root.left,val);
            }else {
                // 递归去右树中查找
                return contains(root.right,val);
            }
        }

        public int findMin() {
            // 判空
            if (size == 0) {
                // 空树
                throw new NoSuchElementException("BST is empty! cannot find min");
            }
            TreeNode minNode = minNode(root);
            return minNode.val;
        }

        public int findMax() {
            // 判空
            if (size == 0) {
                throw new NoSuchElementException("BST is empty! cannot find max");
            }
            TreeNode maxNode = maxNode(root);
            return maxNode.val;
        }

        public int removeMax() {
            int max = findMax();
            root = removeMax(root);
            return max;
        }

        /**
         * 在当前以root为根的BST中删除最大值节点，返回删除后的树根
         * @param root
         * @return
         */
        private TreeNode removeMax(TreeNode root) {
            if (root.right == null) {
                TreeNode left = root.left;
                root.left = root = null;
                size --;
                return left;
            }
            root.right = removeMax(root.right);
            return root;
        }

        /**
         * 在当前BST中删除最小值节点，返回删除的最小值
         * @return
         */
        public int removeMin() {
            int min = findMin();
            root = removeMin(root);
            return min;
        }
        /**
         * 在当前以root为根的BST中删除最小值所在的节点，返回删除后的树根
         * @param root
         * @return
         */
        private TreeNode removeMin(TreeNode root) {
            if (root.left == null) {
                // 当前root就是待删除的节点
                TreeNode right = root.right;
                root.right = root = null;
                size --;
                return right;
            }
            // 递归去左子树中删除
            root.left = removeMin(root.left);
            return root;
        }

        public void remove(int val) {
            root = remove(root,val);
        }

        /**
         * 在当前以root为根节点的BST中删除值为val的节点
         * 返回删除后的新的根节点
         * @param root
         * @param val
         * @return
         */
        private TreeNode remove(TreeNode root, int val) {
            // 边界
            if (root == null) {
                // 把树中所有节点都遍历完还没找到值为val的节点，就不存在值val的节点
                throw new NoSuchElementException("BST 中没有值为"+val+"的节点!");
            }else if (val < root.val) {
                // 此时待删除的节点位于左子树
                root.left = remove(root.left,val);
                return root;
            }else if (val > root.val) {
                // 此时待删除的节点位于右子树
                root.right = remove(root.right,val);
                return root;
            }else {
                // 此时root.val == val
                // root就是待删除的节点
                if (root.left == null) {
                    // 只有右孩子，返回右孩子即可
                    TreeNode right = root.right;
                    root.right = root = null;
                    size --;
                    return right;
                }
                if (root.right == null) {
                    // 只有左孩子
                    TreeNode left = root.left;
                    root.left = root = null;
                    size --;
                    return left;
                }
                // 此时说明root.left 和 root.right 都不为空
                // Hibbard Deletion
                TreeNode successor = minNode(root.right);
                // 在右子树中删除后继节点的时候就已经size --了
                successor.right = removeMin(root.right);
                successor.left = root.left;
                // 将要删除的节点58，和BST断开关系
                root.left = root.right = root = null;
                return successor;
            }
        }

        /**
         * 查询以root为根的BST中最大值节点
         * @param root
         * @return
         */
        private TreeNode maxNode(TreeNode root) {
            if (root.right == null) {
                // root就是最大值所在的节点
                return root;
            }
            return maxNode(root.right);
        }

        /**
         * 在当前以root为根的BST中找最小值所在的节点，返回最小值节点
         * @param root
         * @return
         */
        private TreeNode minNode(TreeNode root) {
            if (root.left == null) {
                // 此时root就是最小值
                return root;
            }
            return minNode(root.left);
        }

        /**
         * 向以root为根的BST中插入一个新的结点val
         * @param root
         * @param val
         * @return
         */
        private TreeNode add(TreeNode root, int val) {
            if (root == null) {
                // 创建新节点
                TreeNode newNode = new TreeNode(val);
                // 当前值就是根节点
                size ++;
                return newNode;
            }
            if (val < root.val) {
                // 左树中插入
                root.left = add(root.left,val);
            }
            if (val > root.val) {
                // 右树插入
                root.right = add(root.right,val);
            }
            return root;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            generateBSTString(root,0,sb);
            return sb.toString();
        }

        /**
         * 先序遍历以root为根的BST，将节点值存储在sb中
         * @param root
         * @param height
         * @param sb
         */
        private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
            // 边界
            if (root == null) {
                sb.append(generatHeightStr(height)).append("NULL\n");
                return;
            }
            sb.append(generatHeightStr(height)).append(root.val).append("\n");
            // 递归访问左子树
            generateBSTString(root.left,height + 1,sb);
            // 递归访问右子树
            generateBSTString(root.right,height + 1,sb);
        }

        /**
         * 按照当前所处的树的层次打印 --
         * 每多一层，就多两个--
         * @param height
         * @return
         */
        private String generatHeightStr(int height) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < height; i++) {
                sb.append("--");
            }
            return sb.toString();
        }
    }